package com.leetcode.divide;

import com.leetcode.basic.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/7/29 21:16
 */
public class GenerateTrees_95 {

    public List<TreeNode> generateTrees(int n) {
        if (n < 1) return new ArrayList<>();
        return generateTrees(1, n);
    }

    public List<TreeNode> generateTrees(int start, int end) {
        LinkedList<TreeNode> nodes = new LinkedList<>();
        if (end < start) {
            // 超过了边界，那么添加null
            nodes.add(null);
            return nodes;
        }
        for (int i = start; i <= end; i++) {
            // 分别生成左右子树的节点集合。以左子树走到头或者以右子树走到头
            // 注意留出根节点
            List<TreeNode> lefts = generateTrees(start, i - 1);
            List<TreeNode> rights = generateTrees(i + 1, end);
            for (TreeNode left : lefts) {
                for (TreeNode right : rights) {
                    // 新建结点，然后将结点添加到集合中
                    TreeNode node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    nodes.add(node);
                }
            }
        }

        return nodes;
    }

    static class Solution {

        public List<TreeNode> generateTrees(int n) {
            if (n < 1) return new LinkedList<>();
            return generateTrees(1, n);
        }

        private List<TreeNode> generateTrees(int start, int end) {
            List<TreeNode> list = new LinkedList<>();

            if (start > end) {
                list.add(null);
                return list;
            }

            for (int i = start; i <= end; i++) {
                List<TreeNode> lefts = generateTrees(start, i - 1);
                List<TreeNode> rights = generateTrees(i + i, end);
                for (TreeNode left : lefts) {
                    for (TreeNode right : rights) {
                        TreeNode node = new TreeNode(i);
                        node.left = left;
                        node.right = right;
                        list.add(node);
                    }
                }
            }
            return list;
        }
    }

}

